package LeetCode;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}17:25
 */
public class LeetCode204 {
    public static void main(String[] args) {
        System.out.println(new LeetCode204().countPrimes(10));
    }

    public int countPrimes(int n) {
        int count = 0;
        boolean[] prime = new boolean[n];
        Arrays.fill(prime,true);
        for (int i = 2; i < n ; i++){
            if (prime[i]){
                for (int j = i * i;j < n;j+=i){
                    prime[j] = false;
                }
            }
        }

        for (int i = 2;i < n;i++){
            if (prime[i]){
                count++;
            }
        }
        return count;
    }
}
